package airthmetic.exercise.hash;

public class _76_最小覆盖子串 {
    public String minWindow(String s, String t) {
        if(s == null || t == null || s.length() ==0 || t.length()==0 || s.length()< t.length()){
            return "";
        }
        // 定义字典 滑动窗口
        int[] dict = new int[128];
        int[] window = new int[128];

        // 字典赋值
        for(int i=0; i< t.length(); i++){
            dict[t.charAt(i)]++;
        }
        // 定义 size
        int size = 0;
        // 定义返回
        String res = "";
        // 定义指针
        int left = 0, right = 0;
        // 定义最小字符串数量
        int strNum = s.length() +1;

        while(right < s.length()){
            window[s.charAt(right)]++;
            if(dict[s.charAt(right)] > 0 && dict[s.charAt(right)] >= window[s.charAt(right)]){ // s:[a,a,b]  t:[a,b,c]
                size++;

            }

            while(size == t.length()){
                while((dict[s.charAt(left)] > 0 && window[s.charAt(left)] > dict[s.charAt(left)]) || dict[s.charAt(left)] == 0){
                    left++;
                }
                size--;

                if (strNum > (right - left)){
                    strNum = (right - left);
                    res = s.substring(left, right);
                }

            }
        }
        return res;
    }

    public static String minWindow2(String s, String t) {
        if (s == null || t == null || s.length() == 0 || t.length() == 0 || s.length() < t.length()) {
            return "";
        }
        // 定义字典 滑动窗口
        int[] dict = new int[128];
        int[] window = new int[128];

        // 字典赋值
        for (int i = 0; i < t.length(); i++) {
            dict[t.charAt(i)]++;
        }
        // 定义 size
        int size = 0;
        // 定义返回
        String res = "";
        // 定义指针
        int left = 0, right = 0;
        // 定义最小字符串数量
        int strNum = s.length() + 1;

        while (right < s.length()) {
            window[s.charAt(right)]++;
            if (dict[s.charAt(right)] > 0 && dict[s.charAt(right)] >= window[s.charAt(right)]) { // s:[a,a,b]  t:[a,b,c]
                size++;

            }
            right++;

            while (size == t.length()) {
                if (dict[s.charAt(left)] > 0 && dict[s.charAt(left)] >= window[s.charAt(left)]) {
                    size--;
                    if (strNum > (right - left)) {
                        strNum = (right - left);
                        res = s.substring(left, right);
                    }
                }

                window[s.charAt(left)]--;
                left++;


            }
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(minWindow2("abc", "ab"));
    }
}
